Generate and Filter による展開ヘルプ
Web の情報やパソコン内データを検索するために様々なテキスト検索システムが利用されている。
計算機や機器の利用に関して疑問な点があれば、とりあえずネットで検索すると必要な情報を得られることが多い。
十分巨大で有用なテキストデータベースが存在すれば、既存のテキスト検索手法を利用してそれなりに有効な検索が可能なのは確かである。
もし、あるコンテクストにおいてシステムが実行可能なことすべてを幅広い表現でリストしたテキストデータベースが存在すれば、そのデータに対して通常のテキスト検索手法を適用することにより、ユーザにとって有効なヘルプ情報を得ることができるはずである。
例えば、ヘルプデータベースの中に「時計を6 時23 分にセットする」「時刻を 7:12 に設定する」のような多様で具体的なテキストが大量に存在すれば、一般的なテキスト検索手法を利用して「時刻」「7:12」のようなキーワードからヘルプ項目を容易に捜し出すことができ、同時に具体的な時刻設定を実行することが可能になる。
また、テキストの曖昧検索を行なうことにより、データの中に「時計」や「時刻」のような文字列しか存在しない場合でも「時間」「7:12」のようなキーワードから「時刻を 7:12 に設定する」のようなヘルプ項目を選択することが可能になる。
あらゆる表現を含むヘルプデータベースをテキストデータとしてあらかじめ作成しておくことは現実的でないが、幅広い表現を機械的に生成することは難しくない。
前述のような問題の場合、「(時刻|時計|時間) を([1-9]?[0-9]) 時に(セットする|設定する|あわせる)」のような正規表現を用意することによって「時計を6 時にセットする」「時刻を7 時に設定する」のような多様な表現を生成することができ、生成されたテキストを検索対象とすることができる。
このとき、文字列を生成するのと同時にユーザが指定した検索文字列でフィルタリングを行なう “Generate and Filter” を行なうことにより、実際にすべてのテキストを展開出力することなく効率的に検索を行なうことができる。 生成されたエントリ項目に対してそれを実行する方法も記述しておけば、検索されたヘルプ項目を選ぶと同時に実行を指令することができる。
また、文字列検索手法として曖昧パタンマッチアルゴリズムを利用すれば、検索文字列がヘルプ項目の記述と多少異なっていた場合でも項目をみつけることができる。
このような技法を統合したヘルプシステムの手法を「展開ヘルプ」と呼ぶことにする。 たとえば8-Queen 問題をGenerate and Test で解こうとする場合、あらゆるQueen の配置を生成しながらその配置が問題の条件を満たしているかを判定し、条件を満たしているものを解として出力する。 8 個のQueen を盤面に配置するには$ \binom{64}{8}(\simeq48億)通りの置き方があるため、これらを素直にすべて生成してから判定を行なうと大量の計算時間が必要であるが、条件にあわない配置は生成の初期段階で無視するような工夫をすることによって高速に解を求めることができる。